package com.yequan.leetcode.queue.mycirculardeque_641;

/**
 * //设计实现双端队列。
 * //你的实现需要支持以下操作：
 * //
 * //
 * // MyCircularDeque(k)：构造函数,双端队列的大小为k。
 * // insertFront()：将一个元素添加到双端队列头部。 如果操作成功返回 true。
 * // insertLast()：将一个元素添加到双端队列尾部。如果操作成功返回 true。
 * // deleteFront()：从双端队列头部删除一个元素。 如果操作成功返回 true。
 * // deleteLast()：从双端队列尾部删除一个元素。如果操作成功返回 true。
 * // getFront()：从双端队列头部获得一个元素。如果双端队列为空，返回 -1。
 * // getRear()：获得双端队列的最后一个元素。 如果双端队列为空，返回 -1。
 * // isEmpty()：检查双端队列是否为空。
 * // isFull()：检查双端队列是否满了。
 * //
 * //
 * // 示例：
 * //
 * // MyCircularDeque circularDeque = new MycircularDeque(3); // 设置容量大小为3
 * //circularDeque.insertLast(1);			        // 返回 true
 * //circularDeque.insertLast(2);			        // 返回 true
 * //circularDeque.insertFront(3);			        // 返回 true
 * //circularDeque.insertFront(4);			        // 已经满了，返回 false
 * //circularDeque.getRear();  				// 返回 2
 * //circularDeque.isFull();				        // 返回 true
 * //circularDeque.deleteLast();			        // 返回 true
 * //circularDeque.insertFront(4);			        // 返回 true
 * //circularDeque.getFront();				// 返回 4
 * // 
 * //
 * //
 * //
 * // 提示：
 * //
 * //
 * // 所有值的范围为 [1, 1000]
 * // 操作次数的范围为 [1, 1000]
 * // 请不要使用内置的双端队列库。
 * //
 * // Related Topics 设计 队列
 *
 * @author : Administrator
 * @date : 2020/3/22
 */
public class MyCircularDeque {

    public static void main(String[] args) {
        MyCircularDeque myCircularDeque = new MyCircularDeque(10);
        myCircularDeque.insertFront(1);
        myCircularDeque.insertFront(2);
        myCircularDeque.insertLast(3);
        myCircularDeque.insertFront(4);
        myCircularDeque.insertLast(5);
        while (!myCircularDeque.isEmpty()){
            System.out.println(myCircularDeque.getRear());
            myCircularDeque.deleteLast();
        }
    }

    /**
     * 设计思路:
     * 1.使用数组存储
     * 2.front,rear指针指示头尾位置
     *  front:队头所在位置:当队头插入时,先将指针往前移(front-1+capacity) % capacity,再赋值;当队头删除时,front移动,即(front+1)%capacity
     *  rear:队尾元素的下一个位置: 当队尾插入时,先赋值,再移动位置(rear+1)%capacity; 当队尾删除时,移动rear为(rear-1+capacity)%capacity
     */

    /**
     * 双端队列容量
     */
    private int capacity;
    /**
     * 使用数组实现双端队列
     */
    private int[] array;
    /**
     * 指向头节点
     */
    private int front;
    /**
     * 指向尾节点下一个位置
     */
    private int rear;

    /**
     * Initialize your data structure here. Set the size of the deque to be k.
     */
    public MyCircularDeque(int k) {
        capacity = k + 1;
        array = new int[capacity];
        front = 0;
        rear = 0;
    }

    /**
     * 当队头插入时,先将指针往前移(front-1+capacity) % capacity,再赋值
     * Adds an item at the front of Deque. Return true if the operation is successful.
     */
    public boolean insertFront(int value) {
        if (isFull()) {
            return false;
        }
        front = (front - 1 + capacity) % capacity;
        array[front] = value;
        return true;
    }

    /**
     * 当队尾插入时,先赋值,再移动位置(rear+1)%capacity
     * Adds an item at the rear of Deque. Return true if the operation is successful.
     */
    public boolean insertLast(int value) {
        if (isFull()) {
            return false;
        }
        array[rear] = value;
        rear = (rear + 1) % capacity;
        return true;
    }

    /**
     * 出队:当队头删除时,front移动,即(front+1)%capacity
     * Deletes an item from the front of Deque. Return true if the operation is successful.
     */
    public boolean deleteFront() {
        if (isEmpty()) {
            return false;
        }
        front = (front + 1) % capacity;
        return true;
    }

    /**
     * 当队尾删除时,移动rear为(rear-1+capacity)%capacity
     * Deletes an item from the rear of Deque. Return true if the operation is successful.
     */
    public boolean deleteLast() {
        if (isEmpty()) {
            return false;
        }
        rear = (rear - 1 + capacity) % capacity;
        return true;
    }

    /**
     * Get the front item from the deque.
     */
    public int getFront() {
        if (isEmpty()) {
            return -1;
        }
        return array[front];
    }

    /**
     * Get the last item from the deque.
     */
    public int getRear() {
        if (isEmpty()) {
            return -1;
        }
        return array[(rear - 1 + capacity) % capacity];
    }

    /**
     * Checks whether the circular deque is empty or not.
     */
    public boolean isEmpty() {
        return front == rear;
    }

    /**
     * Checks whether the circular deque is full or not.
     */
    public boolean isFull() {
        return (rear + 1) % capacity == front;
    }
}
